package com.example.demo.linear;

/**
 * @auther: Bin.L
 * @date: 2021-11-27 17:22
 * @Description: 数组模拟队列 {https://zq99299.github.io/dsalg-tutorial/dsalg-java-hsp/03/02.html#%E6%95%B0%E7%BB%84%E6%A8%A1%E6%8B%9F%E9%98%9F%E5%88%97}
 * {
 * <h3>定义：</h3>
 * 队列：是一个 有序列表，可以用 数组 或 链表 实现。
 * <p>
 * 特点：遵循 先入先出 原则
 * }
 */
public class ArrayQueue {

    public static void main(String[] args) {

        ArrayQueue.SimulationQueue simulationQueue = new ArrayQueue().new SimulationQueue(3);
        // 测试添加元素
        simulationQueue.add(1);
        simulationQueue.add(2);
        simulationQueue.add(3);

        // 打印输出
        simulationQueue.printQueue();
        simulationQueue.get();
        System.out.println("");

        simulationQueue.printQueue();

    }


    /**
     * 模拟数组对列(环形队列)
     * 0	--> front
     * 1
     * 2
     * 3  *
     * 4	--> rear(队列的最后一个元素的下一个位置)
     * <p>
     * empty  = (front == rear)
     * full = (rear + 1)%maxsize == front
     * efficient = (rear + maxsize - front) % maxsize
     */
    class SimulationQueue {
        // 队列最大容量
        private int maxSize;

        // 队列头,指向 队头 的元素
        private int front;

        // 队列尾，指向 队尾 的下一个元素
        private int rear;

        // 用于存储数据，模拟队列
        private int arr[];


        SimulationQueue(int maxSize) {
            this.maxSize = maxSize + 1;
            this.front = 0;
            this.rear = 0;
            this.arr = new int[maxSize];
        }

        /**
         * printf queue
         */
        public void printQueue() {
            for (int i = front; i < size(); i++) {
                int index = i % maxSize;
                System.out.printf("arr[%d] = %d \n", index, arr[index]);
            }
        }

        /**
         * add data
         *
         * @param n
         */
        public void add(int n) {
            if (isFull()) {
                throw new ArrayIndexOutOfBoundsException("The queue is full");
            }
            arr[rear] = n;
            // rear 指向的是下一个位置 (由于是环形队列,需要使用取模的形式来唤醒他的下一个位置)
            rear = (rear + 1) % maxSize;
        }

        /**
         * get data
         *
         * @return
         */
        public int get() {
            isQueueNull();
            int value = arr[front];
            // 需要向后移动，但是由于是环形，同样需要使用取模的方式来计算
            front = (front + 1) % maxSize;
            return value;
        }

        /**
         * get queue head
         *
         * @return
         */
        public int head() {
            isQueueNull();
            return arr[front];
        }

        /**
         * get queue tail
         *
         * @return
         */
        public int tail() {
            isQueueNull();
            // rear - 1 是队尾数据，但是如果是环形收尾相接的时候
            // 那么 0 -1 就是 -1 了，负数时，则是数组的最后一个元素
            return rear - 1 < 0 ? arr[maxSize - 1] : arr[rear - 1];
        }

        /**
         * queue if full
         *
         * @return
         */
        private boolean isFull() {
            return (rear + 1) % maxSize == front;
        }

        /**
         * judge queue if null
         */
        public void isQueueNull() {
            if (front == rear) {
                throw new ArrayIndexOutOfBoundsException("The queue is null");
            }
        }

        public int size() {
            return (rear + maxSize - front) % maxSize;
        }
    }
}

